/*************************************************************************
 * File Name:    test.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sun 27 Oct 2013 10:50:44 AM CST
 * 
 * Description:  
 |
 |-------------------------------------------------------------------------
 | Problem: Copy List with Random Pointer
 |
 | A linked list is given such that each node contains an additional
 | random pointer which could point to any node in the list or null.
 |
 | Return a deep copy of the list.
 |-------------------------------------------------------------------------
 |
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

/*
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */

struct RandomListNode {
    int label;
    RandomListNode *next, *random;
    RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *ans_head, *th;
        map<RandomListNode *, RandomListNode *> place_map;
        
        ans_head = NULL;
        for (RandomListNode *i = head; i != NULL; i = i->next) {
            if (ans_head == NULL) {
                ans_head = new RandomListNode(i->label);
                th = ans_head;
            } else {
                th->next = new RandomListNode(i->label);
                th = th->next;
            }
            th->random = i->random; 
            place_map[i] = th;
        }
        for (RandomListNode *i = ans_head; i != NULL; i = i->next) {
            i->random = place_map[i->random];
        }
        
        return ans_head;
    }
};

class Solution_Net {
/**
 * This is a solution from the internet, a pretty good idea, which
 * does not use any auxiliary storage to solve this problem.
 */
public:
    RandomListNode * copyRandomList(RandomListNode* head) {
        if (head == NULL) return NULL;
        // clone nodes
        RandomListNode * curNode = head;
        while (curNode != NULL) {
            RandomListNode * newNode = new RandomListNode(curNode->label);
            newNode->random = NULL;
            newNode->next = curNode->next;
            curNode->next = newNode;
            curNode = newNode->next;
        }

        // clone randoms
        curNode = head;
        while (curNode != NULL) {
            if (curNode->random != NULL) curNode->next->random = curNode->random->next;
            else curNode->next->random = NULL;
            curNode = curNode->next->next;
        };

        RandomListNode* clonedHead = head->next;
        curNode = head;
        RandomListNode* clonedNode = head->next;

        while(curNode != NULL) {
            curNode->next = curNode->next->next;
            curNode = curNode->next;
            if (clonedNode->next != NULL) {
                clonedNode->next = clonedNode->next->next;
                clonedNode = clonedNode->next;
            }
        }
        return clonedHead;
    };
};

int
main(int argc, char *argv[])
{
    return 0;
}
